/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-03-31
 * Time: 23:20
 */
public class Main {

    public static void main(String[] args) {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initNodes(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);

        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarshall(dist,parentPath);

        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
            System.out.println("************************");
        }
    }

    /**
     *  测试 bellman-ford 求带权值的单源最短路径的算法
     * @param args
     */
    public static void main5(String[] args) {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initNodes(array);
        /*g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);*/

        //负权回路实例
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('y', 's', 1);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', -8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean flg = g.bellmanFord('s', dist, parentPath);
        if(flg) {
            g.printShortPath('s', dist, parentPath);
        }else {
            System.out.println("存在负权回路");
        }
    }

    /**
     *  测试 dijkstra 算法
     * @param args
     */
    public static void main4(String[] args) {
        /*String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initNodes(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);*/

        /*
        搞不定负权值*/
        String str = "sytx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initNodes(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('t', 'y', -7);
        g.addEdge('y', 'x', 3);

        int[] dist = new int[array.length];
        int[] path = new int[array.length];
        g.dijkstra('s',dist, path);

        System.out.println("dasfa");
        g.printShortPath('s', dist, path);
    }



    /**
     *  测试 prim 算法
     * @param args
     */
    public static void main3(String[] args) {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initNodes(array);

        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);

        GraphByMatrix  primTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.prim(primTree,'a'));
        primTree.printGraph();
    }


    /**
     *  测试 kruskal 算法
     * @param args
     */
    public static void main2(String[] args) {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initNodes(array);

        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);

        GraphByMatrix  kMinTree = new GraphByMatrix(str.length(),false);
        kMinTree.initNodes(array);
        System.out.println(g.kruskal(kMinTree));
        kMinTree.printGraph();
    }


    /**
     *  测试 dfs, bfs , 以及节点的 度
     * @param args
     */
    public static void main1(String[] args) {

        GraphByMatrix graph = new GraphByMatrix(4,false);
        char[] array = {'A','B','C','D'};
        graph.initNodes(array);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);
        graph.printGraph();

//        graph.bfs('B');
        graph.dfs('B');
        //System.out.println(graph.getDevOfV('A'));
    }
}
